This invention relates to arbitrating requests by devices in a computer system for a shared resource and more particularly to an arbiter that grants bus requests using a history based arbitration scheme in conjunction with a second hidden arbitration scheme.
Arbiters are used in computer systems to control access to a common bus used by multiple devices. Arbiters typically use arbitration schemes such as fixed priority, round robin, or rotating priority. A fixed priority algorithm assigns a priority to each device on the bus and grants usage based upon the relative priority of the devices making the requests. The round robin scheme has a fixed order and grants bus usage based upon the requestor order and the current user of the bus. The rotating priority scheme changes the priority of requestors based on a fixed algorithm.
The goal of all arbitration schemes is to insure fair access to the shared resource, and to efficiently grant the resource to the correct requestor. The fixed priority scheme is unfair because a high priority requestor can consume all the shared resource, starving the lower priority requestors. The round robin scheme is inefficient because multiple clocks may be required to determine which requestor should be granted the resource. Also round robin schemes have a fixed grant pattern that can result in starvation of particular requestors if request patterns match the round robin grant pattern. Rotating priority schemes are random in their efficiency and fairness based on the algorithm chosen to update device priority.
U.S. Pat. No. 5,481,680 issued Jan. 2, 1996 to Larson et al. describes a history based arbitration scheme. The history based arbitration scheme changes priority for granting devices control of a bus according to the history of previous bus grants and uses the history of past bus grants to grant control of the bus to the requestor serviced longest ago. The device granted the bus waits for the device currently controlling the bus to finish and then begins a new bus transaction.
While waiting for completion of current bus transactions, other devices with higher priority in the history based arbitration scheme (longest time since last bus grant) can request control of the bus. Since the arbiter has already granted the bus to another device, the device with higher history-based priority is unfairly denied control of the bus. Thus, the arbitration scheme in Larson will not fairly grant the bus to the device with the history based highest priority.
A device granted control of the bus may not actually initiate or complete a bus cycle. For example, a device may be reset or decide not to use the bus after the arbiter has already granted the device control of the bus on the next available bus cycle. Bus cycles are wasted or the system is hung up because the device granted control of the bus never conducts or completes the bus transaction.
Accordingly, a need remains for an arbitration scheme that more fairly grants access to shared resources while providing a more efficient and reliable operating environment.